package com.datastructure.test.fouroftotal.self;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SumOfFour {

    public static List<List<Integer>> getListOfFourFromArray(int [] data,int target){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(data);
        int length = data.length;
        for (int i = 0; i < data.length-3; i++) {
            if(i>0&&(data[i-1]==data[i])){
                continue;
            }
            if(data[i]+data[length-3]+data[length-2]+data[length-1]>target){
                break;
            }
            for(int j=i+1;j< data.length;j++){
                int start = j+1;
                int end = data.length-1;
                while (start<end){
                    if(start>j+1&&(data[start-1]==data[start])){
                        start++;
                    }
                    if(data[i]+data[j]+data[start]+data[end]==target){
                        List<Integer> item = new ArrayList<>();
                        item.add(data[i]);
                        item.add(data[j]);
                        item.add(data[start]);
                        item.add(data[end]);
                        res.add(item);
                        while (start<end&&(data[start+1]==data[start])){
                            start++;
                        }
                        while (start<end&&(data[end-1]==data[end])){
                            end--;
                        }
                        start++;
                        end--;
                    } else if(data[i]+data[j]+data[start]+data[end]>target){
                        end--;
                    } else {
                        start++;
                    }
                }
            }
        }
        return res;
    }
}
